﻿#include<stdio.h>

typedef char VertexType;		//顶点
typedef int EdgeType;

#define MAXSIZE 100

typedef struct {
	VertexType vertex[MAXSIZE];		//保存顶点
	EdgeType arc[MAXSIZE][MAXSIZE];		//记录两顶点之间边的关系(是否有边)
	int vertex_num;		//顶点数量
	int edge_num;			//边的数量
}Mat_Grph;		//矩阵的图

int visited[MAXSIZE];		//记录某个顶点是否被访问过

void creat_graph(Mat_Grph* G) {
	G->vertex_num = 9;	//9个节点
	G->edge_num = 15;		//15个无向边
	G->vertex[0] = 'A';
	G->vertex[1] = 'B';
	G->vertex[2] = 'C';
	G->vertex[3] = 'D';
	G->vertex[4] = 'E';
	G->vertex[5] = 'F';
	G->vertex[6] = 'G';
	G->vertex[7] = 'H';
	G->vertex[8] = 'I';
	
	for (int i = 0; i < G->vertex_num; i++) {		//赋值
		for (int j = 0; j < G->vertex_num; j++) {
			G->arc[i][j] = 0;
		}
	}

	//A-B,A-F是有线的
	G->arc[0][1] = 1;
	G->arc[0][5] = 1;

	//BC,BG,BI
	G->arc[1][2] = 1;
	G->arc[1][6] = 1;
	G->arc[1][8] = 1;

	//CD,CI
	G->arc[2][3] = 1;
	G->arc[2][8] = 1;

	//DE,DG,DH,DI
	G->arc[3][4] = 1;
	G->arc[3][6] = 1;
	G->arc[3][7] = 1;
	G->arc[3][8] = 1;

	//EF,EG
	G->arc[4][5] = 1;
	G->arc[4][7] = 1;

	//FG
	G->arc[5][6] = 1;

	//GH
	G->arc[6][7] = 1;

	//上下部分是对称的,把上半部分复制到下半部分
	for (int i = 0; i < G->vertex_num; i++) {		//赋值
		for (int j = 0; j < G->vertex_num; j++) {
			G->arc[j][i] = G->arc[i][j];
		}
	}

}

void dfs(Mat_Grph G, int i) {
	visited[i] = 1;		//已被访问
	printf("%c\n", G.vertex[i]);

	for (int j = 0; j< G.vertex_num; j++) {
		if (G.arc[i][j] == 1 && visited[j] == 0) {	//找到有连线且还没有被访问过的点
			dfs(G, j);
		}
	}
}

int main() {
	Mat_Grph G;
	creat_graph(&G);
	//初始化
	for (int i = 0; i < G.vertex_num; i++) {
		visited[i] = 0;
	}
	dfs(G, 0);		//从第一个顶点0开始
	return 0;
}